1. Field of the Invention
The present invention relates to communication switching methods, in particular packet switching on platforms using an asynchronous transfer mode (ATM) fabric.
2. Description of the Related Art
Many devices, such as layer 2 switches (sometime referred to as bridges) and layer 3 switches (sometime referred to as routers), are being developed based on asynchronous transfer mode (ATM) switch architectures. In an ATM switch, the data enter the device through an ingress port, are switched through an ATM switch fabric, and exit the device through an egress port. Both the ingress and egress ports, as presently known in the art, perform a certain amount of intelligent packet processing and datapath switching functions. Since a typical ATM switch device has multiple input/output ports, the ports are usually grouped together on physical linecards or I/O modules. In some literature, these linecards are referred to as port adapters. Each linecard contains several physical connections to the network and the associated control and processing circuits necessary to manage the logical ports representing the physical network connections. The linecard is also connected to the switch fabric within the switch, and thereby connected to every other linecard in the switch.
One logical element of a model ATM switch, known as the control plane, consists of routing protocol, configuration, and management subsystems. The control plane is typically implemented as part of a central routing processor. It may also be implemented in a distributed or pipelined processing architecture through a shared message-passing interface or similar logical structure known in the art. The term “control plane” can also describe a logical combination of subsystems that defines a central route processor. Regardless of configuration, the control plane establishes the internal connections between ingress and egress ports that provide “any to any” switching.
The organization and terminology used to describe ATM switches is further explicated in Chapter 15 of Roger L. Freeman, Telecommunication System Engineering, 3d ed. (1996), incorporated herein by reference in its entirety. Further technical explanation of ATM networks and switching is to be found in H. J. R. Dutton and P. Lenhard, Asynchronous Transfer Mode (ATM) Technical Overview (2d ed. 1995); Othmar Kyas, ATM Networks (1995); and W. A. Flanagan, ATM User's Guide, (1995), all of which are incorporated herein by reference.
The basic communication unit within the Asynchronous Transfer Mode protocol is the cell. An ATM cell is 53 octets in length, and includes a header and a payload. The cell header occupies 5 octets and the remaining 48 octets are reserved for the payload. The cell destination is identified by a Virtual Path Identifier/Virtual Connection Identifier (“VPI/VCI”) located in the header. The VPI is either 8 or 12 bits in length, depending on whether the link is a Network to Network Interface (“NNI”) or a User Network Interface (“UNI”). The VCI is 16 bits in length. Thus, the VPI and VCI collectively provide a 24 or 28 bit address.
Supporting the total number of connections defined by the VPI/VCI address space would be impractical for most commercial ATM switch applications due to large memory requirements and attendant costs. For this reason, it is common practice to translate the VPI/VCI address space to a smaller address space by address translation techniques. In typical ATM switches, the incoming VPI/VCI address is translated into a smaller, local address space whose width defines the number of connections supported by the switch. This internal-to-the switch, local address is the Incoming Virtual Circuit number or IVC. The cell is directed to one or more ports within the switch based on the IVC. In an output process, a remapping is executed to define an outgoing VPI/VCI address for the cell.
Remapping the outgoing VPI/VCI becomes memory intensive when supporting multicast operation since a single incoming VPI/VCI may spawn multiple VPI/VCIs for transmission. For example, if an ATM switch includes 14 linecards, each having 8 I/O ports, it is possible that one input may spawn 112 outputs. It is theoretically possible to employ a lookup table at each port to remap the outgoing address to the proper destination VPI/VCI. However, such an architecture would be impractical since it would require an inordinately large amount of memory. A more efficient technique for handling multicast cells would therefore be of benefit.
As discussed above, packets of data (also called “cells” in ATM literature) are sent from the ingress port on an internal connection to one or more egress ports, also known as egress interfaces. (In ATM terminology, the terms “port” and “interface” are interchangeable and refer to the external network connection to or from the switch.) There are typically two logical components to the internal connection in an ATM switch. The logical part of the connection between the ingress port and the switch fabric is the incoming virtual circuit (IVC) discussed above. The logical part of the connection between the switch fabric and egress port is called the outgoing virtual circuit (OVC). And, as noted above, an internal connection could be one of two types: a point-to-point connection or a point-to-multipoint connection. The IVC associated with a point-to-multipoint connection is known as a “root” and the corresponding set of (multipoint) OVCs are termed “leaves”.
Each egress port then makes its own decision on how to send the packet out of the switching device. For example, egress port processing determines the outgoing (or “uplink”) VPI/VCI on which to send the packet out of the switch. The egress port also decides the type of encapsulation (e.g., UNI or NNI) to use on the outbound packet based on which virtual LAN (VLAN) or external VC that the packet is to use to leave the switch.
Packet processing is thus distributed between both the ingress and egress ports. The ingress processing tasks include packet parsing, header validation, and address look-up at OSI layer 2 and/or layer 3, as commonly known and used in the art. The layer 2/3 address look-up task determines the next hop (i.e., the path denoted by the uplink VPI/VCI to the next switch or the final packet destination) that the packet will take. This determination also determines the egress interface or port. Since the processing power in both the ingress and egress interfaces is limited, it is important to avoid duplicating processing efforts between the ingress and egress sides of the switch.
In the case of broadcast or multicast traffic, the packet replication necessary to send one packet to multiple destinations is typically performed in the switch fabric. However, since the encapsulation and processing of each packet for a particular outbound interface is unique to each outbound interface, the ingress processing is unable to determine a priori all of the necessary encapsulations for broadcast/multicast packets. In other words, it is not possible for the ingress side to convey all of the necessary forwarding information to the egress side. This means that, for broadcast/multicast packets, the egress interface has to determine at least some of the forwarding information based on information presented to it by the switch fabric.
One approach to egress processing of multicast cells previously used in the art maintains an outgoing virtual circuit table at the egress interface. This OVC table is used by the egress interface to look-up the parameters required for egress processing. U.S. Pat. No. 5,666,361, “ATM Cell Forwarding and Label Swapping Method and Apparatus” to Aznar, et al., incorporated herein by reference in its entirety describes one approach to this problem.
As noted above, the main function of an ATM switch is to receive incoming ATM cells (or “packets” of data, generally) at the input ports of one or more port adapters (linecards) and to redirect those cells to specific output ports (on the same or different linecards) for transmission into the surrounding network. Each cell includes a header containing routing information in the form of a Virtual Path Identifier (VPI) field and a Virtual Cell Identifier (VCI) field. The ATM switch reads these fields in each received cell and performs a table look-up operation in the input port adapter (also known as the ingress linecard) in order to locate the target output adapter for the particular cell. This ingress look-up also determines new VPI/VCI values that are to be written (swapped) into the cell header for use by the next ATM switch along the cell's route.
In some prior art ATM switches, the ingress look-up is performed entirely at the ingress linecard and all information obtained, including the target output port identification and the new VPI/VCI values, must be transferred through the ATM switch to the appropriate output (egress) linecard. In some prior systems, the new VPI/VCI values are written into the cell header before the cell is transferred through the switch fabric to reduce the amount of additional information that must be transferred. An example of such a system is described in W. Fischer et al, “A Scalable ATM Switching System Architecture”, IEEE Journal on Selected Areas in Communication, Vol. 9, No. 8, October 1991, pages 1299-1307, incorporated herein by reference in its entirety.
Depending on packet Quality of Service (QoS) or other packet handling requirements (as currently understood in the art), a cell may need to be directed to one of several specialized egress port queues having specific management and scheduling properties. In fact, the output (egress) port processing requirements for a given cell may be different than that at the input (ingress) port. For example, a class Y VCC connection on a port Pi of a particular input adapter may be aggregated with other such connections into a class A VPC connection on port Pj of an output adapter. Such a case can occur when connecting a Local Area Network (LAN) to a Wide Area Network (WAN) through the ATM switch.
Also known in the prior art is the use of a second look-up table at the output (egress) linecard. Performing an egress table look-up permits cells to be queued on the basis of their QoS properties. It also permits additional or different cell processing operations to be performed on the ingress and egress sides of the switch fabric and, additionally, the assignment of new ATM headers to a switched cell to support multicasting.
FIG. 1 shows the components of a typical ATM switch. A switch fabric 100, capable of switching cells from any of a number of input/output (I/O) leads to any other of such leads, is connected to a switch controller 151 through leads 111 and 113 and to a linecard 102 through leads 103 and 105. Additional linecards, such as linecards 104 and 106, are typically similarly connected to the switch fabric 100 through similar leads (not illustrated). Switch controller 151 includes a control processor 150, which may be a microprocessor. The control processor is connected through a DMA transfer controller 152 to a queuing controller 154 used for queuing data to be delivered to the switch fabric 100 over lead 113. The queuing controller 154 is connected to a processor 158 used to provide ATM layer handling for the queued data. The operations performed by queuing controller 154 and ATM layer processor 158 make use of random access memory (RAM) elements 162 and 166, respectively. Data received from switch fabric 100 over lead 111 is received in a second queuing controller 156 connected both to the DMA transfer controller 152 and to an ATM layer processor 160. The queuing controller 156 and ATM layer processor 160 make use of RAM 164 and 168, respectively.
One of the primary functions of linecards, such as linecard 102, is to concentrate traffic received on a number of ATM ports so that standard ATM cell processing functions, including an ATM Transmission Convergence (TC) sublayer function, can be performed in the switch. The number of linecards that can be included in the switch is a function of the size of the switch fabric 100. Linecard 102 includes a multiplexer 110 for concentrating cells received from different ones of ATM input ports 130 at the ATM UNI (User-to-Network Interface) interface and a de-multiplexer 120 for distributing ATM cells destined for different ones of ATM output ports 131, also at the ATM UNI interface. Different media (such as copper wire or optical fiber) may be used to carry ATM cells. To accommodate the differences in media, physical media-dependent interface circuits 136 and 137 are connected to the multiplexer 110 and demultiplexer 120, respectively. Like the switch controller 151, linecard 102 includes queuing controllers 112 and 122 for ATM data being delivered to and received from the switch fabric 100. Linecard 102 also includes ATM layer processors 116 and 126 for performing ATM layer functions on incoming and outgoing ATM packets. Buffers 112 and 122 are connected to RAM elements 114 and 124, respectively, while the ATM layer processors 116 and 126 are connected to RAM elements 118 and 128, respectively.
In the described arrangement, ATM data received at any of the input ports 130 on linecard 102 can be exchanged with the control processor 150 or with any of the output ports 131 on linecard 102 or corresponding output ports on other linecards, such as linecards 104 and 106.
The ATM switch implementation described above is illustrative of an environment in which the present invention may be implemented. The invention can also be implemented in a more highly integrated system, such as a system in which the control processor and adapter function are integrated into a single device, or in a system using a switching element other than the normal ATM switch fabric. An example of an alternative switch would be a bus.
FIG. 2 describes the paths taken by incoming data received at one of the input ports of linecard 102 in another prior art ATM switching system. In this system, ingress and egress linecards (the port adapters) each contain processing engines that read, process, and rewrite packet information.
The cell follows a path 200 to a specific cell buffer 240 in RAM 114. Source port information SP is delivered to the ATM layer processor 116 on a path 202 along with the ATM header of cell stored in buffer 240 to enable processor 116 to perform the necessary ingress table look-up operation. In a standard ATM cell, the source port information SP is encoded in four bits in the cell while the VPI/VCI fields occupy twenty-eight bits, yielding a thirty-two bit input pattern for the ingress table look-up operation.
The ingress look-up result is the connection identifier (i.e., the incoming virtual circuit identifier, IVC) for the cell. The controller 116 accesses a connection control block address (path 204) in the RAM 118 using the IVC as an index to identify the path to the target (egress) linecard and the proper port on the egress linecard. This lookup, which is performed by the control plane, associates an Outgoing Virtual Circuit (OVC) with the IVC in a table structure maintained by the control plane. The controller also retrieves and stores, in some systems, a field identifying the class of traffic to which the cell belongs. Examples of different classes of traffic are the different Qualities of Service considered standard in ATM technology. As noted above, different classes of traffic can require different processing operations.
The cell is forwarded along a path 210 to switch fabric 100, which uses the IVC and OVC information stored in the control plane to forward the cell to the egress linecard 104.
Once at the egress linecard 104, the cell is written into a cell buffer 250 in RAM 124. IVC, source port information, and ATM header information are extracted from the contents of cell buffer 250 and directed to the ATM layer processor 126 along a path 212. Using this information (and especially the OVC from the control plane), the ATM layer processor 126 performs the egress look-up operation. Using the OVC, the processor 126 accesses the appropriate address in RAM 128 (i.e., from the control plane) to retrieve the uplink VPI/VCI and any additional processing parameters. This RAM space is referred to as the OVC table. Specifically, the retrieved information includes the VPI and VCI values which control the transfer of the cell to a particular egress port Pj and swap control information, such as whether the connection is a VCC (Virtual Channel Connection) or VPC (Virtual Path Connection) and whether the port is a UNI (User-to-Network Interface) or a NNI (Network-to Network Interface).
The information resulting from the egress look-up is forwarded to a label swap function 220 along path 216. The label swap function retrieves the original cell header, including the original VPI and VCI information, from RAM 124 and generates a new cell header (NCH) in accordance with the swap controlling information. The new cell header is written back into the cell buffer 250 along a path 222. The cell, with its newly-modified header, is forwarded to the egress port Pj through the appropriate queue and demultiplexer.
The OVC table size is limited because of the relative scarcity of memory available to support each egress port in a switch, since switches typically contain many ingress and egress ports. This memory limitation puts a restriction on the number of OVCs terminating on a particular egress linecard since each OVC obviously requires a unique virtual circuit identifier (VCI). Typically, the OVC table memory allocation becomes exhausted even before the switch fabric's IVC and OVC capability is completely utilized.
This memory limitation poses a number of problems. Firstly, present designs lack the necessary scalability to support ever increasing needs for L2 bridge group and L3 multicast group support on a given number of external ports. For example, on a switch that supports n bridge groups and p ports, the egress OVC table could have up to (n*p) entries. Furthermore, if the egress port is a ATM uplink which supports m external VCs, then the OVC table must be of a size (m*p). Thus, for a platform that has 256 ports and an ATM uplink (i.e., the egress port to external network connection) that supports 8 K external VCs, the OVC table for the ATM uplink needs to have 2 M entries. One switching device currently in use today, however, incorporates a memory allocation for the OVC table of only 4 K entries.
In addition to the memory size limitation, there is an ancillary problem created by the fact that egress port processing requires an external memory reference to the OVC table to perform the look-up. As the table size necessarily grows, the number of bits for required in the memory reference increases, thus expanding the general processing overhead.
What is needed is a packet processing approach for ATM switching that is scalable to accommodate a continuously increasing demand for a multicast and broadcast group addressing without incurring the memory limitations noted above.